# _*_ coding:utf-8 _*_
__author__ = 'joker_wb'
__date__ = '2018/4/20 17:04'
from math import log
import operator
def calcShannonEnt(dataSet):
    """
    计算熵的公式。熵越高，则混合的数据越多
    :param dataSet:
    :return:
    """
    numEntries=len(dataSet)#计算数据中实例的总数
    labelCounts={}#创建一个数据字典
    for featVec in dataSet:
        currentLabel=featVec[-1]
        if(currentLabel not in labelCounts.keys()):
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1
    shannonEnt=0.0
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries #概率
        shannonEnt-=prob*log(prob,2)
    return shannonEnt



def createDataSet():
    """
    创造一组数据。
    :return:
    """
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels


def splitDataSet(dataSet,axis,value):
    """
    根据数据中的某个特征来划分
    :param dataSet:
    :param axis:
    :param value:
    :return:
    """
    retDataSet=[]
    for featVec in dataSet:
        if(featVec[axis]==value):
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet



def chooseBestFeatureToSplit(dataSet):
    """
    计算按哪个特征分组最好。
    :param dataSet: 传入需要分组的特征
    :return: 返回最好的特征。
    """
    numFeatures=len(dataSet[0])-1
    baseEntropy=calcShannonEnt(dataSet)#计算数据的原始香浓熵
    bestInfoGain=0;bestFeatures=-1
    for i in range(numFeatures):#第一个for循环遍历所有的特征。
        featList=[example[i] for example in dataSet] #将列表中所有第i个值写入新的list中。
        uniqueVals=set(featList)#变成了set数据类型。里面的元素互不相同。
        newEntropy=0
        for value in uniqueVals:
            #在第i个特征中，分类，计算每一堆的香浓熵，然后按比例求和，算出按i特征分的总的香浓熵。
            subDataSet=splitDataSet(dataSet,i,value)
            prob=len(subDataSet)/float(len(dataSet))
            newEntropy+=prob*calcShannonEnt(subDataSet)
        infoGain=baseEntropy-newEntropy
        if(infoGain>bestInfoGain):
            bestInfoGain=infoGain
            bestFeatures=i
    return bestFeatures

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if(vote not in classCount.keys()):
            classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]


def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]

    if classList.count(classList[0]) == len(classList):#当全部相等的时候。
        return classList[0]  # stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1:  # stop splitting when there are no more features in dataSet
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel: {}}
    del (labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]  # copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree


data,label=createDataSet();
mytree=createTree(data,label)
print(mytree)




